import sys
import timeit

def product(x, y):
  n = len(x)
  assert n == len(y), 'invalid matrix'
  sum = 0
  for i in xrange(n):
    sum += x[i] * y[i]
  return sum

def matix_mulipy(x, y):
  assert len(x[0]) == len(y), 'invalid matrix'
  m = len(x)
  n = len(y[0])
  a = len(x[0])
  #transit y
  y = [[y[i][j] for i in xrange(a)] for j in xrange(n)]
  return [[product(x[i], y[j]) for i in xrange(m)] for j in xrange(n)]

def matrixp(mat, n):
  assert n > 0, 'invalid n'
  tmp = mat
  res = None
  while True:
    if n & 1:
      if res == None: res = tmp
      else: res = matix_mulipy(res, tmp)
    n = n >> 1
    if n == 0: break;
    tmp = matix_mulipy(tmp, tmp)
  return res

def fibo(n):
  assert n >= 0, 'invalid n'
  if n < 2: return [0,1][n]
  mat = [[1,1],[1,0]]
  return matrixp(mat, n)[0][0]

def wrapper(func, *args, **kwargs):
  def wrapped():
    return func(*args, **kwargs)
  return wrapped

if __name__ == '__main__':
  if sys.argv < 2:
    print "Usage: {0} num".format(sys.argv[0])
  wrapped = wrapper(fibo, int(sys.argv[1]))
  print timeit.timeit(wrapped, number=1)
